The Kerberos Authentication System - An Intoduction
by x0d
Introduction
------------
This article is an introduction to Kerberos, an authentication system
written at MIT. It covers the security problems that motivated the creation of
Kerberos, the basic mechanisms of the Kerberos protocol and finally some
security flaws in the kerberos ystem. The first section covers some network
security strategies and the problems encountered. The second section goes
through the Kerberos protocol in a step by step fashion. The final section
briefly touches on some known attack plans in breaking Kerberos as well as some
limitations it has when adapted to other environments.
Motivation
----------
Networks allow many computers to convey information amoung each other.
Individual machines need not provide all the services needed by its users but
can rely on remote machines to provide services. Special program called
servers can be run on a specif ed machine, and anytime that service is needed a
program on the remote machine, called a client, can request the service on
behalf of the local machine. The idea of networked servers and clients is well
integrated into modern computing. Sometimes a ser er deals with importaint
personal information such as mail and must know the identity of the user
requesting the data. More than that the server would like to be sure that the
user requesting the service is indeed who he says he is.
Remote servers can authenticate clients trying to access their sevices
in several ways. First the remote server can do nothing. In this case the
remote server is depending on the clients host for authentication. An example
of this is the smtp service
When a client connects to this server it is assumed that all data it
receives is valid. If the client side decides to give false information the
service will gladly accept it, resulting in forged mail. It is up to the
client's host to keep this from appening. A second example is the yp service.
Unless carefully set up any client can connect to and use the remote yp
database server and it is up to the clients host to keep unauthorized users
from using the client (through permissions on the client p ogram). A more
secure authentication can be achieved by having the client's host machine
authenticate itself to the service but then trust any information that host
passes on about the identity of the client. This is the strategy of rlogin,
rsh and the system of 'trusted' hosts. If a connection comes from a rlogin
client on a trusted machine (which is weekly authenticated by the fact that it
has the correct address) then the service will allow the client to login to an
account of the same name. This trategy fails if the clients machine can forge
its address (and hence bypass the authentication) or if the security on the
client's machine has been bypassed allowing the client to take on any username.
In a more ideal authentication system a compromise in security on one machine
wouldn't lead to a compromise in secuity on a remote system.
The authentication system that Kerberos uses is based on an individual
authentication of each client. In this system a client must authenticate
itself for each service it uses. The remote login service offered by the
telnetd server is an example of th s. The client cannot login to a remote
account through the service unless the proper acount name and password where
entered. Although this may sound like a secure operation there is one major
flaw to it. Whenever a password is transmitted over the ne work it is in
danger of being compromised. A third party may be monitoring the network
traffic as it goes by and see the login name and password as they are being
used. This can be more dangerous than using the trusted host paradigm.
It is important to look at the environment that Kerberos was designed
for when looking at Kerberos. Kerberos was designed at MIT for MIT's Project
Athena. The hardware environment there consists of many privately owned and
many publically accessible w rkstations connected in a network with along with
several time-sharing machines which also act as file servers. Many services
are available with servers on many machines in the network. For example many
machines may be running a (modified) rlogin serve . Security of the
workstations cannot be trusted. They may be privately owned machines and the
owner may be free to bypass all security, or they may be rebooted with a
different root file system. Once a user has bypassed the general securities on
the machine he is free to alter his identity, alter his machines address, and
even eaves-drop over the network.
The goals in creating the Kerberos authentication system where based on
the environment. A machines address could not be trusted. The user-id of a
user on a particula machine could not be trusted. Any information sent over
the network should be usele s in attempts to impersonate another user.
c - client Kx - x's private key
s - server Tc,s - Ticket for c to use s
Kc,s - key shared Ax - Authenticator for client x
between c and s {abc}Kx - abc encrypted in key Kx
tgs - ticket granting server life - a tickets lifespan
kerb - authentication server addr - a clients address
Figure 1. Abbreviations.
-------------------------
The kerberos system itself is implemented as a collection of servers.
The two major types of severs in the Kerberos system are authentication servers
(called kerberos servers) and ticket granting servers (often refered to as tgs
in this paper).
Kerberos uses a system of private keys, tickets and authenticators. A
private key is a secret key used for encryption and decryption. Reading a
message encrypted in certain key is only possible if the key is known,
similarly encrypting a message in a certain key is only possible if the key is
known. Kerberos currently uses a modified DES algorithm known as DES cypher
block chaining. Normally DES encrypts each block (an arbitrary group of bits)
seperately but in cypher block chaining encryption of t e second block depends
on the contents of the first block. A ticket is a message (See Figure 2)
{Tc,s} Ks = { s, c, addr, life, Ks,c } Ks
Figure 2. Ticket.
------------------
that allows a client to use a service in much the same way a movie ticket
allows a person to be admitted into the theatre. To prevent a ticket from
being altered it is encrypted in a key known only to the server that the ticket
is intended for. The ticket contains the name of the serve, the name of the
client who can use the ticket, the address of that client, the lifetime for
which t e ticket can be used (tickets usually expire 8 hours after the initial
login), and the key that is shared between the server and client. An
authenticator is a message which contains identification information about a
client. Authenticators are always en rypted in a key shared by the client
sending it and the server it is sent to. Authenticators contain the clients
name, the clients address, and a timestamp. All the clients and servers using
kerberos must have loosely synchronized clocks. Any authent cator older than
five minutes is invalid.
{Ac} Ks,c = { c, addr, timestamp } Ks,c
Figure 3. Authenticator.
-------------------------
Mechanics
---------
Using kerberos involves three processes. First a user must log in.
When logging in the user's client receives a ticket to use the ticket granting
service upon being authenticated. This ticket allows him to use the ticket
granting service which is use in getting tickets for any other service that the
client wants to use. After getting a ticket from the ticket ganting server the
client can use that server until the ticket expires. Since any new ticket
granted has a lifetime that is the same as the ticket used to acquire it, all
tickets expire 8 hours after the initial login (with the exception of certain
tickets with specified shorter lifespa ). This means that if a user remains
online for 8 hours he must re-login. Besides having to re-log in every 8 hours
the entire process is transparent to the user. The login is much like a login
to a non-kerberos system and the additional tickets aquir d during the session
are all aquired without the users intervention.
The goal of the login process is to aquire a ticket to use the ticket
granting service and to authenticate the user. If the user is unable to be
authenticated he should not be able to access the ticket granting server. When
the user walks up to the co puter and enters his login name a message is sent
to the authentication server containing the client's name (that is, the name of
Client ---- c, tgs ----> Kerb
Client <-- { Kc,tgs {Tc,tgs}Ktgs }Kc -- Kerb
Figure 4. Login.
-----------------
the user) and the (See Figure 4)ticket granting service which the client wishes
to use. The kerberos server then builds a ticket (noting the clients name and
address in it) for that tgs and encrypts it in a special key that the tgs
knows. It also creates a session key which will be u ed in conversations
between the client and the tgs. It looks up the clients name and a
corresponding key derived from the users password in its database. It then
encrypts the session key and the ticket in the clients secret key and sends it
back to the client. The user is then prompted for his password. The secret
key is then computed from his password and used to decrypt the message from the
kerberos server. If the user typed in the wrong password the message will not
decrypte properly. If the co rect password is entered the client now holds a
ticket to use the tgs and a key to use when sending messages to the tgs.
Once a client has a ticket to use the tgs it may request more tickets
for other services. The client first builds up an authenticator and encrypts
it in the session key. It then sends a message to the tgs containing the name
of the requested service the ticket to use the tgs and the authenticator. The
tgs first decrypts the ticket with its secret key. In the ticket is the
Client -- s, {Tc,tgs}Ktgs, {Ac}Kc,tgs --> TGS
Client <-- { {Tc,s}Ks, Kc,s }Kc,tgs -- TGS
Figure 5. Getting More Tr.
---------------------------
session key the tgs sends back to the client the ticket and the new key all
encrypted in the key shared between the client and the tgs. When the client
receives the message it just decrypts it and has a ticket for the requested
service and a key to use when talking to it.
To use a service the client first authenticates itself. It does this by building an authenticator, encrypting it in the key shared between the client and the server and sending it to the server along with the ticket to use that server. When the server
gets the ticket it just decrypts the ticket, uses the shared key contained in the ticket to decrypt the authenticator, and compares the information contained in them. If everything matches the client is allowed to use the service and subsequent request
will be allowed. In some cases the client would also like to make sure it is
indeed talking to the real server and not an imposter. The server can validate
itself to the client by taking the timestamp from the authenticator, adding one
to it, and sending it back. If the service was ot the real thing, it would not
have the servers private key, would not be able to read the ticket and get the
Client -- {Ac}Kc,s, {Tc,s}Ks --> Server
Client <-- { timestamp + 1 }Kc,s -- Server
Figure 6. Getting More Tickets.
--------------------------------
shared key, would not be able to read the timestamp and add one to it, and
would not be able to re-encrypt it and send it back. If the client recieves
the incremented timestamp back it can be sure that the server did indeed have
the servers private key.
Along with these three important processes there are many other
supporting processes in the kerberos system. For example there are the
database management processes for adding new users and changing passwords and
there are slave kerberos and tgs server which contain copies of the kerberos
and tgs databases to avoid a bottlenecks. There is also a kerberos network
file system which follows a slightly different protocol in order to avoid the
large number of encryptions that using the kerberos protocol w uld cause.
Security Flaws
--------------
Although Kerberos increases the security of the network it is used on,
it is not flawless. There are several proposed line of attacks that could be
used against the Kerberos protocol, and several limitations that it suffers
when used in an environment ther than the one it was designed for.
Kerberos was designed for a network consisting of many workstations
being used by individual users connected to a few large time-sharing machines
that provide services such as file storage and mail delivery. The keys
accumulated by the client during the session are stored in the /tmp directory
in the current version of Kerberos. If more than one user was logged in on the
same machine it would be possible for one user to view another users session
keys and use them to impersonate that user. On the wor stations Kerberos was
first implemented on the /tmp directory was located on the workstation itself,
but if a diskless workstation was used the keys would have to go over the
network to their destination, and back to the workstation whenever accessed. E
en on workstations with disks, the keys may be swapped out of memory onto the
remote file server if virtual memory is supported. These keys would be easy to
intercept by simply watching the network for access to and files in the
temporary directory or f r swapped out pages. Use of Kerberos is also
problematic when on a large machine with multiple addresses, since each ticket
holds information about only one address. On systems with more than one user
it is possible for users to find out the keys of ot er users logged in at the
same time if they can bypass the security of the temporary files in which they
are stored. Once a user has these keys he can impersonate the other user.
One of the most popular attacks on the Kerberos protocol is replay. An
eaves-dropper can watch as a known client sends an authenticator and ticket to
a server. When that client logs out the eaves-dropper can change his address
to the address the client was using (and hence the address in the authenticator
and the ticket) and change the client name to that of the client. Then the
ticket and authenticator can once the security of one of its hosts has been
compromised. Kerberos was designed to maintain network se urity even in these
circumstances. The mechanisms of encrypted authenticators and tickets was
looked at and in particular the pocesses of getting a ticket for the ticket
ganting service and getting tickets for arbitary services and then using the
services it was looked at. Finally some known flaws and limitations of
Kerberos where looked at and it was seen that Kerberos is not yet completely
secure from attacks.
Bibliography
------------
1. C. H. Meyer and S. M. Matyas, Cryptography: A New dimension in
Computer data Security, John Wiley and Sons, New York (1982).
2. N. Koblitz, A Course in Number theory and Cryptography, Springer-Verlag,
New York (1987).
3. A. Salomaa, Public-Key cryptography, Springer-Verlag, Berlin (1990).
4. J. G. Steiner, C. Neuman and J. I. Schiller, Kerberos: An
Authetication Service for Open Network Systems (Mar. 1988).
5. S. M. Bellovin and M. Meritt, Limitations of the Kerberos Authentication
System, Proc. Winter USENIX Conference, Dallas (1991).
